package com.demo.alg.chapter15动态规划.数塔取数问题;

import java.util.Scanner;
import java.util.Stack;

/**
例题1: 数塔取数问题
一个高度为N的由正整数组成的三角形，从上走到下，求经过的数字和的最大值。
每次只能走到下一层相邻的数上，例如从第3层的6向下走，只能走到第4层的2或9上。

该三角形第n层有n个数字，例如：

第一层有一个数字：5

第二层有两个数字：8 4

第三层有三个数字：3 6 9

第四层有四个数字：7 2 9 5

最优方案是：5 + 8 + 6 + 9 = 28

注意:上面应该是排列成一个三角形的样子不是竖向对应的，排版问题没有显示成三角形。

状态定义: Fi，j是第i行j列项最大取数和，求第n行Fn，m（0 < m < n）中最大值。

状态转移方程：Fi，j = max{Fi-1,j-1,Fi-1,j}+Ai,j
 * @author zhangsulei
 *
 */
public class Dp01 {

	public static void main(String[] args) {
        int n = 4;
        long max = 0;
        int[][] dp = new int[n][n];
        int[][] dpIndex = new int[n][n];
        int[] arr = new int[]{5, 8, 4, 3, 6, 9, 7, 2, 9, 5};
        int index = 0;
        dp[0][0] = arr[index];
        dpIndex[0][0] = index;
        index++;

        for(int i=1;i<n;i++){
            for(int j=0;j<=i;j++){
                int num = arr[index];
                if(j==0){
                    dp[i][j] = dp[i-1][j] + num;
                }else {
                    dp[i][j] = Math.max(dp[i-1][j-1],dp[i - 1][j]) + num;
                }
                dpIndex[i][j] = index;
                index++;
                max = Math.max(dp[i][j], max);
            }
        }
        //[[5, 0, 0, 0], [13, 9, 0, 0], [16, 19, 18, 0], [23, 21, 28, 23]]
        //[[0, 0, 0, 0], [1, 2, 0, 0], [3, 4, 5, 0], [6, 7, 8, 9]]
        String s = "";
        for(int i=0;i<n;i++){
        	int rowMax = 0;
        	int rowIndex = 0;
            for(int j=0;j<=i;j++){
            	if(dp[i][j] > rowMax){
            		rowMax = dp[i][j];
            		rowIndex = j;
            	}
            }
            s = s + arr[dpIndex[i][rowIndex]] + "+";
        }
        System.out.println(s.substring(0, s.length()-1) + "=" +max);
    }

}
